import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import javax.swing.tree.TreeNode;

/*
 * @lc app=leetcode.cn id=101 lang=java
 *
 * [101] 对称二叉树
 *
 * https://leetcode-cn.com/problems/symmetric-tree/description/
 *
 * algorithms
 * Easy (56.77%)
 * Likes:    1696
 * Dislikes: 0
 * Total Accepted:    472.1K
 * Total Submissions: 831.3K
 * Testcase Example:  '[1,2,2,3,4,4,3]'
 *
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 * 
 * 
 * 
 * 
 * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    // 递归
    // public boolean isSymmetric(TreeNode root) {
    //     return root == null || isSymmetricHelp(root.left, root.right);
    // }
    // private boolean isSymmetricHelp(TreeNode left, TreeNode right) {
    //     if(left == null || right == null)
    //         return left == right;
    //     if(left.val != right.val)
    //         return false;
    //     return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right, right.left);
    // }

    // 迭代
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        if(root.left == null || root.right == null) {
            return root.left == root.right;
        }
        boolean ret = true;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root.left);
        queue.add(root.right);
        mark:
        while (!queue.isEmpty()) {
            // 成对出队
            int cnt = queue.size();
            for (int i = 0; i < cnt; i += 2) {
                TreeNode A = queue.poll();
                TreeNode B = queue.poll();
                if (A.val != B.val) {
                    ret = false;
                    break;
                }
                if (A.left == null || B.right == null) {
                    // 判断是否一空一不空
                    if (A.left != B.right) {
                        ret = false;
                        break mark;
                    }
                }
                if (B.left == null || A.right == null) {
                    if (B.left != A.right) {
                        ret = false;
                        break mark;
                    }
                }
                if (A.left != null && B.right != null) {
                    queue.add(A.left);
                    queue.add(B.right);
                } 
                if (B.left != null && A.right != null) {
                    queue.add(B.left);
                    queue.add(A.right);
                }
            }
        }
        return ret;
    }
}
// @lc code=end

